#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    /**
     * @brief 基于比较的排序
     * 
     * @param heights 
     * @return int 
     */
    int heightChecker(vector<int> &heights)
    {
        vector<int> expected(heights);
        sort(expected.begin(), expected.end());
        int n = heights.size(), ans = 0;
        for (int i = 0; i < n; ++i)
        {
            if (heights[i] != expected[i])
            {
                ++ans;
            }
        }
        return ans;
    }
    /**
     * @brief 计数排序
     * 
     * @param heights 
     * @return int 
     */
    int heightChecker_2(vector<int> &heights)
    {
        int m = *max_element(heights.begin(), heights.end());
        vector<int> cnt(m + 1);
        for (int h : heights)
        {
            ++cnt[h];
        }

        int idx = 0, ans = 0;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= cnt[i]; ++j)
            {
                if (heights[idx] != i)
                {
                    ++ans;
                }
                ++idx;
            }
        }
        return ans;
    }
};

int main()
{

    system("pause");
    return 0;
}
